/*#
 #*/
package cn.itaha.algorithm.leetcode.dynamicprogramming;

/**
 * <p>标题：最大正方形</p>
 * <p>功能：</p>
 * <pre>
 * 其他说明：
 * 地址链接：https://leetcode-cn.com/problems/maximal-square/
 * </pre>
 * <p>创建日期：2019年11月27日下午5:08:20</p>
 * <p>类全名：cn.itaha.algorithm.leetcode.dynamicprogramming.Code221MaximalSquare</p>
 * 查看帮助：<a href="" target="_blank"></a>
 *
 * 作者：yinjun 
 * 初审： 
 * 复审：
 * 
 * @version 1.0
 */
public class Code221MaximalSquare
{
	public static void main(String[] args)
	{
		/**
		 * 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
		 * 
		 * 示例:
		 * 
		 * 输入:
		 * 
		 * 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
		 * 
		 * 输出: 4
		 */
		int maximalSquare = maximalSquare02(new char[][] { { '1', '1', '1', '1', '1', '1', '1', '1' }, { '1', '1', '1', '1', '1', '1', '1', '0' }, { '1', '1', '1', '1', '1', '1', '1', '0' },
				{ '1', '1', '1', '1', '1', '0', '0', '0' }, { '0', '1', '1', '1', '1', '0', '0', '0' } });
		System.out.println(maximalSquare);
	}

	/**
	 * 按照边长算
	 * 本题采用动态规划思路:
	 * 		选择正方形右下角作为坐标定点(i,j)
	 * 		记dp[i][j]表示以该定点作为正方形右下角的最大正方形边长
	 * 		则有：
	 * 			dp[i,j] = 1+min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
	 * 		由于给定数组matrix只是用1、0来记录判断图形，数值的大小并不影响原始数据所呈现的正方形影像
	 * 		因此我们可以直接在给定数组matrix上操作，不用新建dp
	 * 				1	0
	 * 				0	(i,j)
	 * 		像上图的情况，我们认为坐标(i,j)的正方形边长为1，面积为1,
	 * 	 			1	1
	 * 				0	(i,j)
	 * 		像上图的情况，我们认为坐标(i,j)的正方形边长为1，面积为1,
	 * 	 			1	0
	 * 				1	(i,j)
	 * 		像上图的情况，我们认为坐标(i,j)的正方形边长为1，面积为1,
	 * 	 			1	1
	 * 				1	(i,j)
	 * 		像上图的情况，我们认为坐标(i,j)的正方形边长为2，面积为4,
	 * 
	 * 时间复杂度：O(n^2)
	 * 空间复杂度：O(1)
	 * 
	 * @param matrix
	 * @return
	 */
	public static int maximalSquare03(char[][] matrix)
	{
		if (matrix == null || matrix.length <= 0)
		{
			return 0;
		}
		int result = matrix[0][0] - '0';
		for (int i = 0; i < matrix.length; i++)
		{
			for (int j = 0; j < matrix[i].length; j++)
			{
				if (i == 0 || j == 0)
				{
					if (result == 0 && matrix[i][j] == '1')
					{
						result = matrix[i][j] - '0';
					}
					continue;
				}
				int rightX = matrix[i][j] - '0';
				int rightS = matrix[i - 1][j] - '0';
				int leftX = matrix[i][j - 1] - '0';
				int leftS = matrix[i - 1][j - 1] - '0';
				if (rightX > 0)
				{
					matrix[i][j] = (char) (1 + Math.min(leftS, Math.min(rightS, leftX)) + '0');
					result = Math.max(result, matrix[i][j] - '0');
				}
			}
		}
		for (int i = 0; i < matrix.length; i++)
		{
			for (int j = 0; j < matrix[i].length; j++)
			{
				System.out.print(matrix[i][j] + "\t");
			}
			System.out.println();
		}
		return result * result;
	}

	/**
	 * 按照面积算(实际原理还是按照边长算)
	 * 
	 * @param matrix
	 * @return
	 */
	public static int maximalSquare02(char[][] matrix)
	{
		if (matrix == null || matrix.length <= 0)
		{
			return 0;
		}
		int result = matrix[0][0] - '0';
		for (int i = 0; i < matrix.length; i++)
		{
			for (int j = 0; j < matrix[i].length; j++)
			{
				if (i == 0 || j == 0)
				{
					if (result == 0 && matrix[i][j] == '1')
					{
						result = matrix[i][j] - '0';
					}
					continue;
				}
				int rightX = matrix[i][j] - '0';
				int rightS = matrix[i - 1][j] - '0';
				int leftX = matrix[i][j - 1] - '0';
				int leftS = matrix[i - 1][j - 1] - '0';
				if (rightX > 0 && rightS > 0 && leftX > 0 && leftS > 0)
				{
					int min = Math.min(rightS, Math.min(leftX, leftS));
					matrix[i][j] = (char) ((min + Math.sqrt(min) * 2 + 1) + '0');
					result = Math.max(result, matrix[i][j] - '0');
				}
			}
		}
		for (int i = 0; i < matrix.length; i++)
		{
			for (int j = 0; j < matrix[i].length; j++)
			{
				System.out.print(matrix[i][j] + "\t");
			}
			System.out.println();
		}
		return result;
	}
}
